#include<vector>
#include<algorithm>
#include<string>
#include<unordered_map>
using namespace std;
class Solution {
private:
    bool findItinerary(vector<string>&path,unordered_map<string, vector<string>>& graph,int max) {
        if (path.size() == max)return true;
        auto it = graph.find(path.back());
        if (it != graph.end()) {
            for (int i = 0; i < it->second.size(); ++i) {
                path.push_back(it->second[i]);
                it->second.erase(it->second.begin() + i);
                if (findItinerary(path, graph, max))
                    return true;
                it->second.insert(it->second.begin() + i, path.back());
                path.pop_back();
            }
        }
        return false;
    }

public:
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        unordered_map<string, vector<string>>graph;
        for (auto& ticket : tickets)
            graph[ticket[0]].push_back(ticket[1]);
        for (auto& it : graph) {
            sort(it.second.begin(), it.second.end());
        }
        vector<string> path = { "JFK" };
        findItinerary(path, graph, tickets.size() + 1);
        return path;
    }
};

int main() {
    vector<vector<string>>tickets = { {"JFK","SFO"},{"JFK","ATL"},{"SFO","ATL"},{"ATL","JFK"},{"ATL","SFO"} };
    Solution sol;
    sol.findItinerary(tickets);
}